package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DivideConquer;
import cn.pugle.oj.catalog.Unknown;

import java.util.Arrays;

/**
 * 啊啊啊啊 二分查找我疯了 错误写法
 *
 * @author tzp
 * @since 2020/10/19
 */
public class LC240 implements DivideConquer {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        return search(matrix, target, 0, matrix.length - 1, 0, matrix[0].length - 1);
    }

    /**
     * 本题查找的是左确界
     */
    public boolean search(int[][] matrix, int target, int rs, int re, int cs, int ce) {
        if (rs > re || cs > ce
                || rs < 0 || re >= matrix.length
                || cs < 0 || ce >= matrix[0].length) return false;
        if (rs == re && cs == ce) return matrix[cs][rs] == target;
        int midR = rs + ((re - rs) >> 1);
        int midC = cs + ((ce - cs) >> 1);

        //两个mid都比target大, 找左上
        //两个mid都比target小, 找除了左上的3个.
        //rowMid比t小, colMid比t大, 找左上, 左下
        if (matrix[midR][cs] == target || matrix[rs][midC] == target) {
            return true;
        } else if (matrix[midR][cs] > target && matrix[rs][midC] > target) {
            return search(matrix, target, rs, midR - 1, cs, midC - 1);//左上
        } else if (matrix[midR][cs] < target && matrix[rs][midC] < target) {
            return search(matrix, target, midR + 1, re, cs, midC - 1) ||//左下
                    search(matrix, target, rs, midR - 1, midC + 1, ce) ||//右上
                    search(matrix, target, midR + 1, re, midC + 1, ce);//右下
        } else if (matrix[midR][cs] < target && matrix[rs][midC] > target) {
            return search(matrix, target, midR + 1, re, cs, midC - 1) ||//左下
                    search(matrix, target, rs, midR - 1, cs, midC - 1);//左上
        } else if (matrix[midR][cs] > target && matrix[rs][midC] < target) {
            return search(matrix, target, rs, midR - 1, midC + 1, ce) ||//右上
                    search(matrix, target, rs, midR - 1, cs, midC - 1);//左上
        } else {
            return false;//never
        }
    }
    //另一种思路是, 我上面比较的时候拿出了两个值和target比较进行分割, 也可以拿出四个值比较进行分割.

    public static void main(String[] args) {
        int[][] m = {
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        };
//        for (int i = 1; i < 19; i++) {
//            System.out.println(new LC240().searchMatrix(m, i));
//        }
        System.out.println(new LC240().searchMatrix(m, 4));
    }
}
